Computer networks are dynamic systems that need be adapted to accommodate temporal and spatial variation of traffic demand. The increasing versatility of network-elements motivates structural changes and the introduction of new services which, in turn, influence the volume and distribution of traffic.
An accurate record of a network's layout is of paramount importance in resolving service disruption as well as in planning network enhancement. The layout of a rapidly changing network is difficult to determine by manual means. As the number of nodes increases, the number of alternative inter-nodal connection patterns increases rendering network-design rather challenging. Detecting, diagnosing and correcting localized malfunctions also become more intricate as the number of interconnected nodes increases.
In addition to real-time control, there is a need for a comprehensive and efficient network design and provisioning system. Conventional network-planning systems are semi-automated, fragmented, and strenuous.
Previous attempts to develop automated network-topology discovery tools applicable to Ethernets may be classified into two categories. The first is based on Address Forwarding Table (AFT) and the second is based on Spanning Tree Protocol (STP).
In a paper entitled “Topology Discovery in Heterogeneous IP Networks”, published in the Proceedings of IEEE INFOCOM'2000, Breitbart et al. propose a discovery technique based on necessary and sufficient condition of complementary relationships of addressing tables of two directly connected switches on specific ports. The technique applies to a network employing the “Simple Network Management Protocol (SNMP)”, which is employed in network-management systems to monitor network devices to detect conditions that warrant administrative attention.
In an ideal scenario, with all forwarding tables complete and all SNMP-enabled devices, the technique generates layer-2 topology. In the case of address incompleteness, an empirical solution is proposed. The technique is not applicable to a network employing switches and hubs which do not implement the SNMP.
In a paper entitled “Topology Discovery in Heterogeneous IP Networks: The Net-Inventory System”, published in IEEE/ACM Transactions on Networking, June 2004, Breitbart et al. extend the discovery technique to handle multiple subnets. However, no solution is provided for a case of AFT incompleteness.
In a paper entitled “Topology Discovery for Large Ethernet Networks”, published in the Proceedings of ACM SIGCOMM, San Diego, Calif., August 2001, Lowekamp et al. propose mutual exclusion of complements of addressing tables as a criterion for determining the topology. However, the mutual exclusion condition does not hold true if multiple subnets are present and connections cannot be established between certain ports using the condition.
In a paper entitled “Physical Topology Discovery for Large Multi-Subnet Networks”, published in the Proceedings of INFOCOM'2003, San Francisco, April 2003, Bejerano et al. present a technique applicable to a network comprising multiple subnets. The technique also adopts a principle of constraint-based elimination.
In a paper titled “Taking The Skeletons Out of the Closets: A Simple and Efficient Topology Discovery Scheme for Large Ethernet LANs”, published in the Proceeding of INFOCOM 2006, Barcelona, Spain, April 2006, Bejerano presents a computationally efficient solution for Layer-2 topology discovery.
All the above works are based on forwarding tables in switches.
In a paper entitled “Layer-2 Path Discovery Using Spanning Tree MIBs”, Avaya Labs Research, March 2002, Scott presents a technique based on spanning trees as formed by spanning tree algorithms to derive the layer-2 topology of a network. Essentially, a stabilized spanning tree itself completely represents connections between the switches. The technique applies to layer-2 networks employing the Spanning-Tree Protocol (STP). Unlike the forwarding table approach, the computational effort for determining the connectivity of switches is negligible. Many layer-2 networks, however, do not deploy the STP protocol or any of its variants.
Automated topology discovery of a layer-2 Ethernet network presents various technical challenges. These challenges are primarily due to (i) existence of hubs and unmanaged switches in a network, (ii) minimal deployment of standardized MAC connectivity discovery protocol such as IEEE 802.1ab and (iii) heterogeneity of layer-2 switches in a network.
There is a need, therefore, for an efficient method and system for network topology discovery which would be suitable for Ethernet network and avoid shortcomings of the prior art. Such a method need be adaptable for implementation in an automated network appliance for real-time network monitoring and analysis to expedite diagnostics and trouble-shooting and, hence, ensure service quality and continuity.